package innersort;

/*
 * 快速排序
 * */
public class QuickSort extends BaseSort {
    public static void main(String[] args) {
        int[] array = {23, 45, 17, 11, 13, 89, 72, 26, 3, 17, 11, 13};
        sort(array, 0, array.length - 1);
    }

    private static void sort(int[] array, int start, int end) {
        if (end <= start) {
            return;
        }

        int temp = array[start];
        int i = start, j = end;

        while (i < j) {
            while (i < j && array[j] >= temp) {
                j--;
            }

            array[i] = array[j];
            print(array, temp, i, j);

            while (i < j && array[i] <= temp) {
                i++;
            }
            array[j] = array[i];
            print(array, temp, i, j);
        }
        array[i] = temp;
        print(array, temp, i, j);
        System.out.println("-----------------------------------------------------------------------------");
        sort(array, start, i);
        sort(array, i + 1, end);
    }
}
